import copy

class Solution(object):
    def __init__(self):
        self.results = []

    def combine(self, begin, k, n, combination):
        if n==0 and k==0:
            self.results.append(copy.copy(combination))
            return
        for i in range(begin, 10):
            if i<=n:
                combination.append(i)
                self.combine(i+1, k-1, n-i, combination)
                combination.pop()
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        self.combine(1, k, n, [])
        return self.results

print(Solution().combinationSum3(3,9))